#include "AVL.h"


void AVL::AVL_clear(node* p) {
	if (p->left) AVL_clear(p->left);
	if (p->right) AVL_clear(p->right);
	delete p;
}


inline void AVL::AVL_LL_rotate(node*& p) {
	node *t = p;
	p = t->left;
	t->left = p->right;
	p->right = t;
	t->balance = -(++p->balance);
}

inline void AVL::AVL_RR_rotate(node*& p) {
	node *t = p;
	p = t->right;
	t->right = p->left;
	p->left = t;
	t->balance = -(--p->balance);
}


inline void AVL::AVL_LR_rotate(node*& p) {
	node *t = p;
	node *l = t->left;
	p = l->right;
	l->right = p->left;
	t->left = p->right;
	p->right = t;
	p->left = l;
	if (p->balance != 1) {
		l->balance = 0;
		t->balance = -p->balance;
	} else {
		l->balance = -1;
		t->balance = 0;
	}
	p->balance = 0;
}

inline void AVL::AVL_RL_rotate(node*& p) {
	node *t = p;
	node *l = t->right;
	p = l->left;
	l->left = p->right;
	t->right = p->left;
	p->left = t;
	p->right = l;
	if (p->balance != -1) {
		l->balance = 0;
		t->balance = -p->balance;
	} else {
		l->balance = 1;
		t->balance = 0;
	}
	p->balance = 0;
}


bool AVL::AVL_insert(node*& p) {
	if (!p) {
		p = new node(*tdata);
		size_var++;
		return true;
	}
	if (*tdata < p->data) {
		if (!AVL_insert(p->left))
			return false;
		if (p->balance != -1)
			return --p->balance;
		if (p->left->balance != 1)
			AVL_LL_rotate(p);
		else
			AVL_LR_rotate(p);
		return false;
	}
	if (p->data < *tdata) {
		if (!AVL_insert(p->right))
			return false;
		if (p->balance != 1)
			return ++p->balance;
		if (p->right->balance != -1)
			AVL_RR_rotate(p);
		else
			AVL_RL_rotate(p);
		return false;
	}
	return false;
}

bool AVL::AVL_delete(node*& p) {
	if (!p) return false;
	if (*tdata < p->data) {
		if (!AVL_delete(p->left))
			return false;
		if (p->balance != 1)
			return !++p->balance;
		if (p->right->balance != -1) {
			AVL_RR_rotate(p);
			return !p->balance;
		}
		AVL_RL_rotate(p);
		return true;
	}
	if (p->data < *tdata) {
		if (!AVL_delete(p->right))
			return false;
		if (p->balance != -1)
			return !--p->balance;
		if (p->left->balance != 1) {
			AVL_LL_rotate(p);
			return !p->balance;
		}
		AVL_LR_rotate(p);
		return true;
	}
	tnode = p;
	if (!p->left) p = p->right;
	else if (!p->right) p = p->left;
	else {
		bool r = AVL_delmin(p->right);
		tnode->balance = p->balance;
		tnode->left = p->left;
		tnode->right = p->right;
		delete p;
		size_var--;
		p = tnode;
		if (!r) return false;
		if (p->balance != -1)
			return !--p->balance;
		if (p->left->balance != 1) {
			AVL_LL_rotate(p);
			return !p->balance;
		}
		AVL_LR_rotate(p);
		return true;
	}
	delete tnode;
	size_var--;
	return true;
}


bool AVL::AVL_delmin(node*& p) {
	if (p->left) {
		if (!AVL_delmin(p->left))
			return false;
		if (p->balance != 1)
			return !++p->balance;
		if (p->right->balance != -1) {
			AVL_RR_rotate(p);
			return !p->balance;
		}
		AVL_RL_rotate(p);
		return true;
	}
	tnode = p;
	p = p->right;
	return true;
}

void AVL::AVL_copy(node*& p, node* rp) {
	p = new node(rp->data, rp->balance);
	if (rp->left) AVL_copy(p->left, rp->left);
	if (rp->right) AVL_copy(p->right, rp->right);
}

//void AVL::AVL_print(node* p) const {
//	if (p->left) AVL_print(p->left);
//	std::cout << p->data << ' ';
//	if (p->right) AVL_print(p->right);
//}

int AVL::AVL_check(node* p) const {
	int l = 0, r = 0;
	if (p->left) {
		l = AVL_check(p->left);
		if (l < 0) return -1;
	}
	if (p->right) {
		r = AVL_check(p->right);
		if (r < 0) return -1;
	}
	if (r - l != p->balance)
		return -1;
	return (l > r ? l : r) + 1;
}

AVL::AVL(void):
	root(0), size_var(0) {}

AVL::AVL(const AVL& param):
	root(0), size_var(param.size_var) {
	if (param.root) {
		try {
			AVL_copy(root, param.root);
		} catch (...) {
			clear();
			throw;
		}
	}
}


AVL::~AVL(void) {
	clear();
}

bool AVL::empty(void) const {
	return size_var == 0;
}

unsigned int AVL::size(void) const {
	return size_var;
}

void AVL::clear(void) {
	if (root) AVL_clear(root);
	root = 0;
	size_var = 0;
}

bool AVL::find(const int& d) const {
	node *p = root;
	while (p)
		if (d < p->data)
			p = p->left;
		else if (p->data < d)
			p = p->right;
		else return true;
	return false;
}


void AVL::insert(const int& d) {
	tdata = &d;
	AVL_insert(root);
}


void AVL::extract(const int& d) {
	tdata = &d;
	AVL_delete(root);
}

//void AVL::print(void) const {
//	if (root) AVL_print(root);
//}

bool AVL::check(void) const {
	if (root && AVL_check(root) < 0)
		return false;
	return true;
}
